/**
*   Copyright (c) Rich Hickey. All rights reserved.
*   The use and distribution terms for this software are covered by the
*   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
*   which can be found in the file CPL.TXT at the root of this distribution.
*   By using this software in any fashion, you are agreeing to be bound by
* 	 the terms of this license.
*   You must not remove this notice, or any other, from this software.
**/

package com.codecommit.collection

import BitVector._

/**
 * A straight port of Clojure's <code>PersistentVector</code> class.
 *
 * @author Daniel Spiewak
 * @author Rich Hickey
 */
class BitVector[+T] private (val length: Int, shift: Int, root: Array[Any], tail: Array[Any]) extends RandomAccessSeq[T] {
  
  def this() = this(0, 5, EMPTY_ARRAY, EMPTY_ARRAY)
  
  final val tailoff = length - tail.length
  
  def apply(i: Int): T = {
	if (i >= 0 && i < length) {
	      if (i >= tailoff) {
		    tail(i & 0x01f).asInstanceOf[T]
	      } else {
		    var arr = root
		    var level = shift
		    while (level > 0) {
			  arr = arr((i >>> level) & 0x01f).asInstanceOf[Array[Any]]
			  level -= 5
		    }
		    
		    arr(i & 0x01f).asInstanceOf[T]
	      }
	} else throw new IndexOutOfBoundsException(i.toString)
  }
      
      def update[A >: T](i: Int, obj: A): BitVector[A] = {
	    if (i >= 0 && i < length) {
		  if (i >= tailoff) {
			val newTail = new Array[Any](tail.length)
			Array.copy(tail, 0, newTail, 0, tail.length)
			newTail(i & 0x01f) = obj
			
			new BitVector[A](length, shift, root, newTail)
		  } else {
			new BitVector[A](length, shift, doAssoc(shift, root, i, obj), tail)
		  }
	    } else if (i == length) {
		  this + obj
	    } else throw new IndexOutOfBoundsException(i.toString)
      }
      
      private def doAssoc[A >: T](level: Int, arr: Array[Any], i: Int, obj: A): Array[Any] = {
	    val ret = new Array[Any](arr.length)
	    Array.copy(arr, 0, ret, 0, arr.length)
	    
	    if (level == 0) {
		  ret(i & 0x01f) = obj
	    } else {
		  val subidx = (i >>> level) & 0x01f
		  ret(subidx) = doAssoc(level - 5, arr(subidx).asInstanceOf[Array[Any]], i, obj)
	    }
	    
	    ret
      }
      
      def +[A >: T](obj: A): BitVector[A] = {
	    if (tail.length < 32) {
		  val newTail = new Array[Any](tail.length + 1)
		  Array.copy(tail, 0, newTail, 0, tail.length)
		  newTail(tail.length) = obj
		  
		  return new BitVector[A](length + 1, shift, root, newTail)
	    } else {
		  var (newroot, expansion) = pushTail(shift - 5, root, tail, null)
		  var newshift = shift
		  
		  if (expansion != null) {
			newroot = array(newroot, expansion)
			newshift += 5
		  }
		  
		  new BitVector[A](length + 1, newshift, newroot, array(obj))
	    }
      }
      
      private def pushTail(level: Int, arr: Array[Any], tailNode: Array[Any], expansion: Any): (Array[Any], Any) = {
	    val newChild = if (level == 0) tailNode else {
		  val (newChild, subExpansion) = pushTail(level - 5, arr(arr.length - 1).asInstanceOf[Array[Any]], tailNode, expansion)
		  
		  if (subExpansion == null) {
			val ret = new Array[Any](arr.length)
			Array.copy(arr, 0, ret, 0, arr.length)
			
			ret(arr.length - 1) = newChild
			
			return (ret, null)
		  } else subExpansion
	    }
	    
	    //expansion
	    if (arr.length == 32) {
		  (arr, array(newChild)) 
	    } else {
		  val ret = new Array[Any](arr.length + 1)
		  Array.copy(arr, 0, ret, 0, arr.length)
		  ret(arr.length) = newChild
		  
		  (ret, null)
	    }
      }
      
      def pop: BitVector[T] = {
	    if (length == 0) {
		  throw new IllegalStateException("Can't pop empty vector")
	    } else if (length == 1) {
		  new BitVector[T]
	    } else if (tail.length > 1) {
		  val newTail = new Array[Any](tail.length - 1)
		  Array.copy(tail, 0, newTail, 0, newTail.length)
		  
		  new BitVector(length - 1, shift, root, newTail)
	    } else {
		  var (newroot, pTail) = popTail(shift - 5, root, null)
		  var newshift = shift
		  
		  if (newroot == null) {
			newroot = EMPTY_ARRAY
		  }
		  
		  if (shift > 5 && newroot.length == 1) {
			newroot = newroot(0).asInstanceOf[Array[Any]]
			newshift -= 5
		  }
		  
		  new BitVector(length - 1, newshift, newroot, pTail.asInstanceOf[Array[Any]])
	    }
      }
      
      private def popTail(shift: Int, arr: Array[Any], pTail: Any): (Array[Any], Any) = {
	    val newPTail = if (shift > 0) {
		  val (newchild, subPTail) = popTail(shift - 5, arr(arr.length - 1).asInstanceOf[Array[Any]], pTail);
		  
		  if (newchild != null) {
			val ret = new Array[Any](arr.length)
			Array.copy(arr, 0, ret, 0, arr.length)
			
			ret(arr.length - 1) = newchild
			
			return (ret, subPTail)
		  }
		  subPTail
	    } else if (shift == 0) {
		  arr(arr.length - 1)
	    } else pTail
	    
	    //contraction
	    if (arr.length == 1) {
		  (null, newPTail)
	    } else {    
		  val ret = new Array[Any](arr.length - 1)
		  Array.copy(arr, 0, ret, 0, ret.length)
		  
		  (ret, newPTail)
	    }
      }
      
      override def equals(other: Any) = other match {
	    case vec:BitVector[T] => {
		  var back = length == vec.length
		  var i = 0
		  
		  while (i < length) {
			back &&= apply(i) == vec.apply(i)
			i += 1
		  }
		  
		  back
	    }
	    
	    case _ => false
      }
}

object BitVector {
      private[collection] val EMPTY_ARRAY = new Array[Any](0)
      
      def apply[T](elems: T*) = elems.foldLeft(new BitVector[T]) { _ + _ }
      
      @inline
      private[collection] def array(elems: Any*) = {
	    val back = new Array[Any](elems.length)
	    Array.copy(elems, 0, back, 0, back.length)
	    
	    back
      }
}
